#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义栈的最大容量
#define MAX_SIZE 100

typedef struct {
    char items[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, char item) {
    if (isFull(s)) {
        printf("Stack is full\n");
        exit(EXIT_FAILURE);
    }
    s->items[++s->top] = item;
}

// 出栈操作
char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return s->items[s->top--];
}

// 查看栈顶元素
char peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return s->items[s->top];
}

// 判断括号字符串是否有效
bool isValidParentheses(char *s) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; s[i] != '\0'; i++) {
        char currentChar = s[i];

        if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
            push(&stack, currentChar);
        } else {
            if (isEmpty(&stack)) {
                return false;
            }

            char topElement = pop(&stack);
            if ((currentChar == ')' && topElement != '(') ||
                (currentChar == '}' && topElement != '{') ||
                (currentChar == ']' && topElement != '[')) {
                return false;
            }
        }
    }

    return isEmpty(&stack);
}

int main() {
    char test1[] = "()";
    char test2[] = "()[]{}";
    char test3[] = "(]";
    char test4[] = "([)]";
    char test5[] = "{[]}";

    printf("%s: %s\n", test1, isValidParentheses(test1) ? "true" : "false");
    printf("%s: %s\n", test2, isValidParentheses(test2) ? "true" : "false");
    printf("%s: %s\n", test3, isValidParentheses(test3) ? "true" : "false");
    printf("%s: %s\n", test4, isValidParentheses(test4) ? "true" : "false");
    printf("%s: %s\n", test5, isValidParentheses(test5) ? "true" : "false");

    return 0;
}



